#include <iostream>
#include <cmath>
#include <vector>
#include <climits>
using namespace std;

// 0-1背包问题
int value[] = {9, 11, 4, 7, 8};  // 物品价值
int weight[] = {12, 5, 8, 9, 6}; // 物品重量
int lenth = sizeof(value) / sizeof(value[0]);
int c = 30; // 背包容量
int cur_c = 0;  //当前背包容量
int cur_v = 0;  //当前背包价值
int r = 0;      //未处理的物品价值

vector<int> x;     // 背包暂存物品,重量
vector<int> bestX; // 最优解

int maxValue = INT_MIN;
void func(int i)
{
    if (i == lenth)
    {
        int sumValue = 0;
        for(auto v : x)
        {
            sumValue += v;
        }
        if(sumValue > maxValue)
        {
            maxValue = sumValue;
            bestX = x;
        }
    }
    else
    {
        r -= value[i];
        if(cur_c + weight[i] <= c)
        {
            cur_v += value[i];
            cur_c += weight[i];
            x.push_back(value[i]);
            func(i + 1);    //走左子树，选择该节点
            x.pop_back();
            cur_c -= weight[i];
            cur_v -= value[i];
        }
        if(cur_v + r > maxValue)
        {
            func(i + 1);    //走右子树，不选择该节点
        }

        r += value[i];
    }
}
int main()
{
    for(auto i : value)
    {
        r += i;
    }
    func(0);
    for(auto i : bestX)
    {
        cout << i << " ";
    }
    cout << endl;
}

#if qi
int arr[] = {12, 6, 7, 11, 3, 9, 9};
const int lenth = sizeof(arr) / sizeof(arr[0]);
// 给定一组数字，选择元素相加等于k的一组元素。
// 这里选择穷举法
int number = 18;
vector<int> x; // 存储选择的数字
int sum;       // 记录选择数字的和
void func(int i, int number)
{
    if (number == 0)
    {
        for (auto v : x)
        {
            cout << v << " ";
        }
        cout << endl;
    }
    else
    {
        for (int k = i; k < lenth; ++k)
        {
            if (number >= arr[k])
            {
                x.push_back(arr[k]);
                func(k + 1, number - arr[k]);
                x.pop_back();
            }
        }
    }
}
int main()
{
    func(0, number);
}
#endif
#if di
// 给定一组数字，选择元素相加等于k的一组元素。
int k = 18;
vector<int> x;     // 存储选择的数字
vector<int> bestX; // 记录最终选择的元素的数组
int r;             // 未处理的数字，用于剪左枝
int sum;           // 记录选择数字的和
void func(int i)
{
    if (i == lenth)
    {
        if (sum == k)
        {
            bestX = x;
            return;
        }
    }
    else
    {
        r -= arr[i]; // 未处理-1
        if (sum + arr[i] <= k)
        {
            sum += arr[i];
            x.push_back(arr[i]);
            func(i + 1); // 走向左孩子选择当前节点
            sum -= arr[i];
            x.pop_back();
        }
        if (sum + r >= k)
        {
            func(i + 1); // 走向右孩子不选择当前节点
        }
        r += arr[i]; // 把它再放回未处理的
    }
}
int main()
{
    for (int i : arr)
    {
        r += i;
    }
    func(0);
    for (int i : bestX)
    {
        cout << i << " ";
    }
    cout << endl;
}
#endif
#if k
// 给定2n个数，从中选择一组元素n个，使当前选择的减去未被选择的差值最小。

vector<int> x;     // 子集树选定数组。
vector<int> bestX; // 记录最优解
int sum;           // 记录选定元素的和
int spares;        // 记录未选定元素的和
int min_ = INT_MAX;
int left_ = lenth; // 记录未选择的元素的个数

void func(int i)
{
    if (i == lenth)
    {
        if (x.size() < lenth / 2)
        {
            return;
        }
        // 到达叶子节点，得到子集树的一个解
        int result = abs(sum - spares);
        if (result < min_)
        {
            min_ = result;
            bestX = x;
        }
    }
    else
    {
        left_--;
        if (x.size() < lenth / 2) // 剪左枝，不够我才选择，够了我就不选了，还未选够n个
        {
            x.push_back(arr[i]);
            sum += arr[i];
            spares -= arr[i];
            func(i + 1); // 遍历i的左孩子，选择i号位元素
            sum -= arr[i];
            spares += arr[i];
            x.pop_back();
        }
        // 已选择的数字的个数 + 未来能选择的所有个数  < n。那么就不走这个分支了，走了也选不够n个。
        if ((x.size() + left_) >= lenth / 2)
        {
            func(i + 1); // 遍历i的右孩子，不选择i号位元素
        }
        left_++;
    }
}
int main()
{
    for (int i : arr)
    {
        spares += i;
    }
    func(0);
    cout << "min : " << min_ << endl;
    for (auto i : bestX)
    {
        cout << i << " ";
    }
    cout << endl;
}

#endif

#if x
// 给定一组数组，从中选择一组元素使当前选择的减去未被选择的差值最小
int x[lenth] = {0}; // 子集树辅助数组，元素代表走向左孩子还是右孩子，表示数据选择还是不选择
int min_ = 0xFFFFFF;
int sum = 0;    // 选择的元素的和
int spares = 0; // 未选择元素的和
int bestx[lenth] = {0};

void func(int i)
{
    if (i == lenth)
    {
        int result = abs(sum - spares);
        if (result < min_)
        {
            min_ = result;
            for (int j = 0; j < lenth; j++)
            {
                bestx[j] = x[j];
            }
        }
    }
    else
    {
        // 选择i
        x[i] = 1;
        sum += arr[i];
        spares -= arr[i];
        func(i + 1);
        sum -= arr[i];
        spares += arr[i];
        // 不选择i
        x[i] = 0;
        func(i + 1);
    }
}

int main()
{
    for (int i = 0; i < lenth; i++)
    {
        spares += arr[i];
    }
    func(0);

    int result[lenth] = {0};
    for (int i = 0; i < lenth; i++)
    {
        if (bestx[i] == 1)
        {
            result[i] = arr[i];
        }
    }

    cout << "min : " << min_ << endl;
    for (int i = 0; i < lenth; i++)
    {
        cout << result[i] << " ";
    }
    cout << endl;
}

#endif

// 子集树代码
#if 0
void func(int arr[],int i,int len,int x[])
{
    if(i == len)
    {
        for(int j = 0;j < len;j++)
        {
            if(x[j] == 1)
            {
                cout << arr[j] << " ";
            }
        }
        cout << endl;
    }
    else 
    {
        x[i] = 1;//选择节点
        func(arr,i + 1,len,x);//遍历左孩子
        x[i] = 0;//不选择节点
        func(arr,i + 1,len,x);//遍历右孩子
    }
}

int main()
{
    int arr[] = {1,2,3};
    const int lenth = sizeof(arr) / sizeof(arr[0]);
    int x[lenth] = {0};
    func(arr,0,lenth,x);
}
#endif
